#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int x,y,z,next;
}E[2000000+5];
struct Node {
	int k;
	long long dis;
};
inline bool operator<(Node  a,Node  b){
	return a.dis>b.dis;
}
int int_stage[1000000+5];
long long dis[1000000+5];
int cnt=0,elast[100000+5];

inline void add_edge(int x,int y,int z){
	cnt++;
	E[cnt].x=x;
	E[cnt].y=y;
	E[cnt].z=z;
	E[cnt].next=elast[x];
	elast[x]=cnt;
}
inline void dijkstra(int a){
	dis[a]=0;
	priority_queue<Node> q;
	Node tmp;
	tmp.k=a,tmp.dis=0;
	q.push(tmp);
	while(!q.empty()){
		int qk=q.top().k;
		q.pop();
		if(int_stage[qk]) continue;
		if(qk==0) break;
		int_stage[qk]=1;
		for(int j=elast[qk];j;j=E[j].next){
			int Ey=E[j].y;
			if(dis[Ey]>dis[qk]+E[j].z){
				dis[Ey]=dis[qk]+E[j].z;
				tmp.k=Ey,tmp.dis=dis[Ey];
				q.push(tmp);
			}
		}
	}
}
inline int read(){
    int x;
    scanf("%d",&x);
    return x;
}
int main(){
	int n=read();
	for(int i=0;i<=(n);i++) dis[i]=0x3f3f3f3f;
	for(int i=0;i<n;i++){
		add_edge(i,(10*i)%n,0);
		add_edge(i,(1 +i)%n,1);
		if(i>=1)add_edge(n,i,i);
	}
	dijkstra(n);
	printf("%lld\n",dis[0]);
}